package com.nowcoder.code.hjnc;

import java.util.ArrayList;

public class NC119 {

    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        if (k < input.length) {
            quickSortK(input, k, 0, input.length - 1);
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }

    public void quickSortK(int[] input, int k, int start, int end) {

        if (start == end) {
            return;
        }

        int os = start;
        int oe = end;
        int mid = input[os];

        while (start < end) {
            while (start < end && input[end] > mid) {
                end--;
            }
            while (start < end && input[start] <= mid) {
                start++;
            }

            int tmp = input[start];
            input[start] = input[end];
            input[end] = tmp;
        }

        int tmp = input[os];
        input[os] = input[start];
        input[start] = tmp;

        if (start > k) {
            quickSortK(input, k, os, start - 1);
        } else if (start < k) {
            quickSortK(input, k, start + 1, oe);
        }


    }

    public static void main(String[] args) {
        int[] is = {4, 5, 1, 6, 2, 7, 3, 8};
        System.out.println(new NC119().GetLeastNumbers_Solution(is, 1));

    }

}
